Zig-zag product について

), and produces a graph that approximately inherits the size of the large one but the degree of the small one. An important property of the zig-zag product is that if

H

is a good expander, then the expansion of the resulting graph is only slightly worse than the expansion of

G

.
Roughly speaking, the zig-zag product

G \circ H

replaces each vertex of

G

with a copy (cloud) of

H

, and connects the vertices by moving a small step (zig) inside a cloud, followed by a big step (zag) between two clouds, and finally performs another small step inside the destination cloud.
The zigzag product was introduced by . When the zig-zag product was first introduced, it was used for the explicit construction of constant degree expanders and extractors. Later on the zig-zag product was used in computational complexity theory to prove that symmetric logspace and logspace are equal .
==Definition==
Let

G

be a

D

-regular graph on

()

with rotation map

\mathrm_G

and let

H

be a

d

-regular graph on

()

with rotation map

\mathrm_H

.
The zig-zag product

G \circ H

is defined to be the

d^

-regular graph on

() \times ()

whose rotation map

\mathrm_

is as follows:

\mathrm_((v,a),(i,j))

:
# Let

(a',i') = \mathrm_ (a,i)

.
# Let

(w,b')=\mathrm_(v,a')

.
# Let

(b,j')=\mathrm_(b',j)

.
# Output

((w,b),(j',i'))

.

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「Zig-zag product」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース